This invention relates to associative memories that find the location of a string of characters in a memory that matches a string of characters presented as an input.
Artificial intelligence (AI) systems often require the retrieval of an item of information from an unknown location in memory. Associative memory circuits are known that find the location of a string of characters in memory that matches a string of characters presented as an input. These circuits typically compare stored computer bytes (each byte representing a character) with input bytes, one input byte at a time. The comparison process typically involves passing a "match" signal from memory byte to memory byte as consecutive bytes in memory match consecutive bytes of a string of characters presented as an input. See, for example, Almy et al., U.S. Pat. No. 4,575,818, "Apparatus for In Effect Extending the Width of an Associative Memory by Serial Matching of Portions of the Search Pattern," Mar. 11, 1986.
Such known circuits are of limited help in most artificial intelligence systems because the item of information sought to be retrieved is typically a syntax that includes variables, rather than a specific identifier. For example, an artificial intelligence system for translating computer programming commands from one format to another may require the retrieval of a stored "dictionary" entry in which a sentence with variables is translated into one or more other sentences with the same variables. A typical such dictionary entry might be "`Do !v1 after .revreaction.v2`means `Do !v2. Do !v1.`" (!v1 and !v2 indicate variables.) The dictionary entry tells the artificial intelligence system to translate, for example, "Do run after compile," to "Do compile. Do run."